package com.xiaolin.algorithm.search.insert;

/**
 * @ClassName InsertValueSearch
 * @Description 插值查找，与二分查找类似，但是检索效率高，因为其mid索引位置是自适应的
 * @Detail 要求数组有序
 * @Author MyPC
 * @Date 2020/11/17
 * @Version 1.0
 */
public class InsertValueSearch {
    public int search(int[] arr,int ele){
        return search(arr,0,arr.length-1,ele);
    }

    private int search(int[] arr,int first,int last,int ele){
        // 要加上条件 ele<arr[first] || ele > arr[arr.length-1] ，否则mid可能会越界
        if(first>last || ele<arr[first] || ele > arr[arr.length-1]){
            return -1;
        }
        // 插值表达式计算mid
        int mid=first+(ele-arr[first])*(last-first)/(arr[last]-arr[first]);
        if(arr[mid] == ele){
            return mid;
        }else if(arr[mid] > ele){
            return search(arr,first,mid-1,ele);
        }else {
            return search(arr,mid+1,last,ele);
        }
    }
}
